package java学习.leetcode.editor.cn;

import java.util.logging.Level;

/**
 * @author 刘世锦
 * 2022-10-18 21:49:13	 当前时间
 */
//给你一个字符串 s ，请你反转字符串中 单词 的顺序。 
//
// 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。 
//
// 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。 
//
// 注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。 
//
// 
//
// 示例 1： 
//
//
//输入：s = "the sky is blue"
//输出："blue is sky the"
// 
//
// 示例 2： 
//
// 
//输入：s = "  hello world  "
//输出："world hello"
//解释：反转后的字符串中不能存在前导空格和尾随空格。
// 
//
// 示例 3： 
//
// 
//输入：s = "a good   example"
//输出："example good a"
//解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 104 
// s 包含英文大小写字母、数字和空格 ' ' 
// s 中 至少存在一个 单词 
// 
//
// 
// 
//
// 
//
// 进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。 
// Related Topics 双指针 字符串 
// 👍 673 👎 0

public class 反转字符串中的单词{
	public static void main(String[] args) {
		Solution solution = new 反转字符串中的单词().new Solution();
		String s = "the sky is blue";
//		String s = "  a good   example  ";
		System.out.println(solution.trim(s));
		System.out.println(solution.trimString(s));
//		System.out.println(solution.trimString1(s));

		System.out.println(solution.reverseWords(s));
	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

	//
//输入：s = "the sky is blue"
//输出："blue is sky the"

	public String reverseWords(String s) {
		StringBuilder trimString = trimString1(s);
		reverseEveryWords(trimString);

		return trimString.toString();
	}

//	翻转每个单词： 先找到每个单词的末尾。
//	翻转的条件： 不仅仅是找到' ' 后翻转，还有末尾的单词也要翻转。(末尾的单词没有' ')
	private void reverseEveryWords(StringBuilder trimString) {
		int i = 0,j = 0;
		while (j<trimString.length()){
		// 找到单词的末尾
		while (i<trimString.length()&&trimString.charAt(i)!=' ') {
			i++;
		}
		reverseAllString(trimString,j,i-1);
		j = i + 1; i++;
		}
	}
	public void reverseAllString(StringBuilder string,int start,int end){
		 while (start<end){
		 	char temp = string.charAt(start);
		 	string.setCharAt(start,string.charAt(end)); ;
		 	string.setCharAt(end,temp);
		 	start++;end--;
		 }
	}

	public StringBuilder trimString(String s){
		String trim = s.trim();
		StringBuilder res = new StringBuilder();
		for (int i = 0; i < trim.length(); i++) {
			if (trim.charAt(i)==' '&&i>0){
				if (trim.charAt(i-1)!=' '){
					res.append(trim.charAt(i));
				}
			}else if (trim.charAt(i)!=' '){
				res.append(trim.charAt(i));
			}

		}

		return res.reverse();
	}
	public StringBuilder trimString1(String s){
		String trim = trim(s);
		StringBuilder res = new StringBuilder();
		for (int i = 0; i < trim.length(); i++) {
			if (trim.charAt(i)==' '&&i>0){
				if (trim.charAt(i-1)!=' '){
					res.append(trim.charAt(i));
				}
			}else if (trim.charAt(i)!=' '){
				res.append(trim.charAt(i));
			}

		}
		reverseAllString(res,0,res.length()-1);
		return res;
	}

	private String trim(String s) {
		int start = 0,n = s.length(),end = n-1;
			while (s.charAt(start)==' '){
				start++;
			}
			while (s.charAt(end)==' '){
				end--;
			}
		return s.substring(start,end+1);
	}
	public String reverseWordsBefore(String s) {
//		1.去除中间、两边多余的空格。
		StringBuilder stringBuilder = removeSpace(s);
		System.out.println(stringBuilder.toString());

//		2. 整体翻转
		stringreverse(stringBuilder,0,stringBuilder.length()-1);
//		3. 局部翻转每个单词
		localreverse(stringBuilder);
		System.out.println(stringBuilder.toString());
		return stringBuilder.toString();
	}

	private void localreverse(StringBuilder stringBuilder) {
		int start = 0; int end = 0,n = stringBuilder.length();
		while (start<n){
			while (end<n&&stringBuilder.charAt(end)!=' '){
				end++;
			}
			stringreverse(stringBuilder,start,end-1);
			start = end+1;
			end ++;
		}
	}

	private void stringreverse(StringBuilder stringBuilder, int start, int end) {
		while (start<end){
			char tmp = stringBuilder.charAt(start);
			stringBuilder.setCharAt(start,stringBuilder.charAt(end));
			stringBuilder.setCharAt(end,tmp);
			start++;end--;
		}
	}

	/**
	 * 去除多余的空格。
	 */
	private StringBuilder removeSpace(String s) {
		StringBuilder builder = new StringBuilder();
		int start = 0,end = s.length()-1;
		// 首先去除两边
		while (start<=end&&s.charAt(start)==' '){
			start++;
		}
		while (end>=start&&s.charAt(end)==' '){
			end--;
		}
		// 去除中间的多余的空格。
		while (start<=end){
			if (s.charAt(start)!=' '){
				builder.append(s.charAt(start));
			}else if (builder.charAt(builder.length()-1)!=' '){
				builder.append(s.charAt(start));
			}
			start++;
		}
		return builder;
	}

	public String reverseWords3(String s) {
		StringBuilder sb = trimSpaces(s);

		// 翻转字符串
		reverse(sb, 0, sb.length() - 1);

		// 翻转每个单词
		reverseEachWord(sb);
		System.out.println(sb.toString());
		return sb.toString();
	}

	public StringBuilder trimSpaces(String s) {
		int left = 0, right = s.length() - 1;
		// 去掉字符串开头的空白字符
		while (left <= right && s.charAt(left) == ' ') {
			++left;
		}

		// 去掉字符串末尾的空白字符
		while (left <= right && s.charAt(right) == ' ') {
			--right;
		}

		// 将字符串间多余的空白字符去除
		StringBuilder sb = new StringBuilder();
		while (left <= right) {
			char c = s.charAt(left);
	// 现在遍历到空格了，若当前字符串的最后一位是空格，则不需要再加空格。(跳过)
	//  若不是空格，再加入空格，确保单词间只会留一位空格
			if (c != ' ') {
				sb.append(c);
			} else if (sb.charAt(sb.length() - 1) != ' ') {
				sb.append(c);
			}

			++left;
		}
		return sb;
	}

	public void reverse(StringBuilder sb, int left, int right) {
		while (left < right) {
			char tmp = sb.charAt(left);
			sb.setCharAt(left++, sb.charAt(right));
			sb.setCharAt(right--, tmp);
		}
	}

	public void reverseEachWord(StringBuilder sb) {
		int n = sb.length();
		int start = 0, end = 0;

		while (start < n) {
			// 循环至单词的末尾
			while (end < n && sb.charAt(end) != ' ') {
				++end;
			}
			// 翻转单词
			reverse(sb, start, end - 1);
			// 更新start，去找下一个单词
			start = end + 1;
			++end;
		}
	}

	public String reverseWords2(String s) {
		String[] split = s.split(" ");
		int n = split.length;
		StringBuilder sb = new StringBuilder();
		for (int i = n - 1; i >= 0; i--) {
			if (!("".equals(split[i]))) {
				sb.append(split[i]);
				sb.append(" ");
			}
		}
		String str = sb.toString().trim();
		System.out.println(str);
		return str;
	}

}
//leetcode submit region end(Prohibit modification and deletion)

}
